521,滑动窗口解最大连续1的个数 III
There is no pressure when you are making a dream come true.
当你是在为梦想成真努力时,就不会有压力。
问题描述
给定一个由若干0和1组成的数组A,我们最多可以将K个值从0变成1。
返回仅包含1的最长(连续)子数组的长度。
示例 1:
输入:
A=[1,1,1,0,0,0,1,1,1,1,0],K=2
输出:6
解释:
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从0翻转到1,最长的子数组长度为6。
示例 2:
输入:
A=[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1],
K=3
输出:10
解释:
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从0翻转到1,最长的子数组长度为10。
提示:
1<=A.length<=20000
0<=K<=A.length
A[i]为0或1
滑动窗口解决
这题让求的是仅包含1的最长连续子数组,并且我们还有魔法,可以把K个0变为1。这题使用滑动窗口解决应该是最容易理解的。
我们可以使用两个指针,一个指向窗口的左边,一个指向窗口的右边,每次遍历数组的时候窗口左边的指针先不动,窗口右边的指针始终都会往右移动,然后顺便统计窗口内0的个数,如果0的个数大于K的时候,说明我们即使使用魔法,也不能把窗口内的所有数字都变为1,这个时候我们在移动窗口左边的指针,直到窗口内0的个数不大于K为止……,具体可以参照下图
来看下代码
1public int longestOnes(int[] A, int K) {
2 int left = 0;//窗口左边的位置
3 int maxWindow = 0;//窗口的最大值
4 int zeroCount = 0;//窗口中0的个数
5 for (int right = 0; right < A.length; right++) {
6 if (A[right] == 0) {
7 zeroCount++;
8 }
9 //如果窗口中0的个数超过了K,要缩小窗口的大小,直到0的个数
10 //不大于K位置
11 while (zeroCount > K) {
12 if (A[left++] == 0)
13 zeroCount--;
14 }
15 //记录最大的窗口
16 maxWindow = Math.max(maxWindow, right - left + 1);
17 }
18 return maxWindow;
19}
其实还可以换种思路,当窗口内0的个数刚好大于K的时候(也就是zeroCount+1==K),说明这个时候right指向的肯定是0,那么目前为止最大的窗口大小是(right-1)-left,因为窗口的右指针是一直往右滑动的,我们可以通过改变左指针的位置来缩小窗口。
所以right-left(注意这里的left已经执行++了,在下面的第10行)始终指向的是最大窗口的值,最后我们只需要返回right-left即可,不需要while循环,来看下代码
1public int longestOnes(int[] A, int K) {
2 int left = 0;//窗口左边的位置
3 int right = 0;//窗口右边的位置
4 int zeroCount = 0;//窗口中0的个数
5 for (; right < A.length; right++) {
6 if (A[right] == 0) {
7 zeroCount++;
8 }
9 //如果窗口中0的个数超过了K,要缩小窗口的大小
10 if (zeroCount > K && A[left++] == 0)
11 zeroCount--;
12 }
13 return right - left;
14}
或者还可以更简洁一些,其实原理都一样,换汤不换药。
1public int longestOnes(int[] A, int K) {
2 int left = 0;//窗口左边的位置
3 int right = 0;//窗口右边的位置
4 int zeroCount = 0;//窗口中0的个数
5 for (; right < A.length; right++) {
6 zeroCount += 1 - A[right];
7 if (zeroCount > K)
8 zeroCount -= 1 - A[left++];
9 }
10 return right - left;
11}
总结
滑动窗口和回溯算法其实都有一个经典的模板,对于回溯算法可以看下450,什么叫回溯算法,一看就会,一写就废。而滑动窗口问题,首先要使用两个指针,一个确定窗口的左边界,一个确定窗口的右边界,其中左边界不动,右边界往右移动,每移动一步都要判断窗口内的值是否满足条件,如果满足,要记录下最优值。如果不满足,左边界在开始移动,相当于缩小窗口……。滑动窗口的题有很多,有时间再对滑动窗口做个总结。
截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有800多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。